import java.util.ArrayList;
import java.util.List;

public class num229 {
    //摩尔投票两个候选人
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> list = new ArrayList<>();
        int count1 = 0,count2 = 0;
        int num1 = 0,num2 = 0;
        for(int i : nums) {
            //第一个候选人存在
            if(count1 > 0 && num1 == i) {
                count1 ++;
            }else if (count2 > 0 && num2 == i) {
                //第二个候选人存在
                count2 ++;
            }else if(count1 == 0) {
                //第一个候选人不存在
                num1 = i;
                count1 ++;
            }else if(count2 == 0){
                //第二个候选人不存在
                num2 = i;
                count2 ++;
            }else {
                //都不相同，票数都减
                count1 --;
                count2 --;
            }
        }
        int vote1 = 0;
        int vote2 = 0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] == num1) {
                vote1 ++;
            }
            if(nums[i] == num2) {
                vote2 ++;
            }
        }
        if (count1 > 0 && vote1 > (nums.length / 3)) {
            list.add(num1);
        }
        if(count2 > 0 && vote2 > (nums.length / 3)) {
            list.add(num2);
        }
        return list;
    }
}
